home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / c / rdcf.exe / CACHE.DOC < prev    next >
Text File  |  1993-01-15  |  14KB  |  348 lines
  1.                     A Simple Reentrant Cache System
  2.                              Version 1.1
  3.  
  4.                        by Philip J. Erdelsky
  5.                        CompuServe 75746,3411
  6.                  InterNet 75746.3411@compuserve.com
  7.  
  8.                         September 15, 1992
  9.  
  10.                PUBLIC DOMAIN -- NO RESTRICTIONS ON USE
  11.  
  12. 0. What's New
  13. -------------
  14.  
  15. The following features were not in version 1.0:
  16.  
  17.   (1) The cache system keeps track of the number of empty, clean and dirty
  18.       sectors.
  19.  
  20.   (2) When flushing the cache, the cache system does not quit on the first
  21.       error. It continues flushing.
  22.  
  23. 1. Introduction
  24. ---------------
  25.  
  26. Many applications that use disks tend to read and write the same sectors
  27. repeatedly. A technique called caching can make such applications run much
  28. faster. With this technique, frequently used sectors are read into memory
  29. buffers when the application begins. The application then reads and writes the
  30. memory buffers. When the application terminates, the buffers are written to
  31. the disk. Since reading and writing memory buffers is much faster than reading
  32. or writing disk sectors, the application can run much faster. There are some
  33. problems with caching. For example, it can be difficult to determine which
  34. sectors will be used frequently. However, the technique is widely used because
  35. the improvement is often quite substantial.
  36.  
  37. This cache system is a simple one, designed to be placed between the Reentrant
  38. DOS-Compatible File System (RDCF) and a disk driver.
  39.  
  40. A single cache can be used for two or more drives, as long as they all have
  41. the same sector size. The cache system is not reentrant with respect to
  42. different drives in this case, so access to it must be serialized.
  43.  
  44. The cache system can handle as many separate caches as available memory
  45. permits. It is fully reentrant with respect to different caches. However,
  46. separate caches may not access the same drive.
  47.  
  48. The cache system calls the standard C functions malloc() and free() when a
  49. cache is being initialized or freed, so reentrancy of those functions is
  50. required at those times. However, it does no memory allocation or deallocation
  51. at other times.
  52.  
  53. The number of sectors in the cache and the size of each sector are determined
  54. at run time and need not be the same for all caches. The only limit to the
  55. number of sectors in the cache is available memory. A cached sector need not
  56. correspond to a single sector on disk, but it must be treated as such by
  57. functions that call and are called by the cache system.
  58.  
  59. Each cache can handle up to 32,768 drives, numbered from 0 to 32,767, and up to
  60. 65,536 sectors on each drive, numbered from 0 to 65,535. The use of larger
  61. numbers will produce numeric overflow and catastrophic failure. Drive numbers
  62. and sector numbers need not be consecutive.
  63.  
  64. No cache system can be optimal in every conceivable case, no matter how
  65. cleverly it is programmed. This cache system uses one of the simplest methods,
  66. and it is apparently adequate for some purposes. You are welcome to make your
  67. own improvements, but you must assume responsibility for the results if you
  68. make a mistake.
  69.  
  70. In this cache system, each cached sector may exist in any of three states:
  71.  
  72.      (1) An EMPTY sector bears no relation to any disk sector.
  73.  
  74.      (2) A CLEAN sector contains the same data as the corresponding disk
  75.          sector.
  76.  
  77.      (3) A DIRTY sector contains data which is to be written to the
  78.          corresponding disk sector but has not yet been written.
  79.  
  80. The cache system attempts to keep each sector in the cache as long as it can,
  81. and it uses the least-recently-used criterion when cached sectors must be
  82. reused. The process is explained in greater detail in Section 4.
  83.  
  84. The source code for the cache system consists of the file CACHE.C and the
  85. header file CACHE.H. The latter should be #included in any source file that
  86. calls on the cache system, because it contains prototypes for all cache
  87. functions and other necessary information.
  88.  
  89. The cache system calls on the following standard C functions:
  90.  
  91.      malloc()
  92.      free()
  93.      memcpy()
  94.  
  95. To prevent identifier conflicts, all publicly defined identifiers in the cache
  96. system begin with the characters "cache", "CACHE" or "_CACHE".
  97.  
  98.  
  99. 2. How the Cache Reads and Writes a Sector
  100. ------------------------------------------
  101.  
  102. The cache system does not read or write the disk directly. You must provide it
  103. with a pointer to a function that you have written for your implementation. The
  104. cache system then calls this function whenever it needs to read or write a disk
  105. sector. The format of the function call is as follows:
  106.  
  107.      e = (*drive_access)(write, drive, sector, buffer);
  108.  
  109.      int write;        nonzero (true) for a write operation; zero (false)
  110.                        for a read operation
  111.  
  112.      unsigned drive;   drive to be read or written
  113.  
  114.      unsigned sector;  sector to be read or written
  115.  
  116.      void *buffer;     address of memory buffer to receive or supply data
  117.  
  118.      unsigned e;       zero for a successful operation, or an
  119.                        implementation-defined nonzero error code
  120.  
  121. When the cache receives a nonzero value from this function, it aborts the cache
  122. operation and returns the value as its own functional value. The cache control
  123. block contains the drive and sector numbers of the offending operation in the
  124. members error_drive and error_sector, respectively. This is especially helpful
  125. for diagnostic purpose, because the error almost always occurs in a sector
  126. other than the one currently being accessed by the application.
  127.  
  128.  
  129. 3. Creating and Initializing a Cache
  130. ------------------------------------
  131.  
  132. The following function call creates and initializes a cache:
  133.  
  134.      q = cache_initialize(drive_access, number_of_sectors, sector_size);
  135.  
  136.      unsigned (*drive_access)();  pointer to function called by cache
  137.                                   to read or write a sector
  138.  
  139.      unsigned number_of_sectors;  number of sectors to be stored in cache
  140.                                   (must be at least 1)
  141.  
  142.      unsigned sector_size;        number of bytes in a sector (1-65,535)
  143.  
  144.      struct cache *q;             pointer to cache control block, or NULL
  145.                                   if there was insufficient memory
  146.  
  147. The function calls on malloc() to allocate memory for the cache storage. If
  148. malloc() returns NULL at any point in the process, the function calls free()
  149. to release any memory that it has allocated and returns a NULL pointer.
  150. Otherwise, it returns a pointer that can be passed to other cache functions.
  151. It marks all sectors in the cache as empty.
  152.  
  153. A sector size near the upper limit of 65,535 may cause numeric overflow and
  154. catastrophic failure if the implementation does not permit allocation of single
  155. objects larger than 65,535 bytes.
  156.  
  157.  
  158. 4. Reading or Writing Through the Cache
  159. ---------------------------------------
  160.  
  161. The heart of the cache system is the following function call:
  162.  
  163.      e = cache_access(q, write, drive, sector, buffer);
  164.  
  165.      struct cache *q;  pointer to cache control block received from
  166.                        cache_initialize()
  167.  
  168.      int write;        nonzero (true) for a write operation; zero (false)
  169.                        for a read operation
  170.  
  171.      unsigned drive;   drive to be read or written
  172.  
  173.      unsigned sector;  sector to be read or written
  174.  
  175.      void *buffer;     address of memory buffer to receive or supply data
  176.  
  177.      unsigned e;       zero for a successful operation, or an
  178.                        implementation-defined nonzero error code
  179.  
  180. This function writes or reads the specified sector to or from the specified
  181. drive, using the cache as follows:
  182.  
  183.     (1) If the specified sector is not already in the cache, a cache sector
  184.         is assigned to it as follows:
  185.  
  186.          (a) If there are still empty sectors in the cache, one of them is
  187.              assigned to the specified sector.
  188.  
  189.          (b) If there are no empty sectors, but there are some clean ones,
  190.              the least-recently used clean sector is marked as